home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 2717 < prev    next >
Encoding:
Text File  |  1996-08-05  |  2.2 KB  |  85 lines
  1. Path: news.mel.aone.net.au!usenet
  2. From: clyde@hitech.com.au (Clyde Smith-Stubbs)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Examples on hashing - help
  5. Date: Tue, 23 Jan 1996 12:00:26 GMT
  6. Organization: HI-TECH Software
  7. Message-ID: <3104cd53.194778240@news.bne.aone.net.au>
  8. References: <1996Jan22.164501@omega.ntu.ac.sg>
  9. Reply-To: clyde@hitech.com.au
  10. NNTP-Posting-Host: skyhawk.hitech.com.au
  11. X-Newsreader: Forte Agent .99c/16.141
  12.  
  13. On 22 Jan 96 16:45:01 +0800, sz7210563@omega.ntu.ac.sg wrote:
  14.  
  15. >I am currently working on a project that requires me to implement chained
  16. >hashing.  Being new to hashing, I would like to ask if anybody has any C 
  17. >examples of the implementation of chained hash tables, including the basic
  18. >functions such as insert, delete, search, traverse etc
  19.  
  20. Here's an example - stripped down from a real application. Need to
  21. define struct sym, and choose a value for SYM_TAB (size of hash
  22. table). It should be a prime number.
  23.  
  24.  
  25. struct sym *    sym_tab[SYM_TAB];
  26.  
  27. short
  28. hashit(char *s, unsigned hash)
  29. {
  30.     register unsigned    i;
  31.  
  32.     i = 0;
  33.     while(*s)
  34.         i += i + (unsigned char)*s++;
  35.     return(i % hash);
  36. }
  37.  
  38. struct sym *
  39. lkupsy(char * s)
  40. {
  41.     register struct sym *    sy, ** pp;
  42.  
  43.     pp = &sym_tab[hashit(s, SYM_TAB)];
  44.     sy = *pp;
  45.     while(sy && strcmp(sy->s_name, s) != 0))
  46.         sy = sy->s_next;
  47.     if(sy)
  48.         return sy;
  49.     sy = (struct sym *)xalloc(sizeof *sy);
  50.     sy->s_next = *pp;
  51.     *pp = sy;
  52.     sy->s_name = xalloc((unsigned)sylen+1);
  53.     strcpy(sy->s_name, s);
  54.     return(sy);
  55. }
  56.  
  57.  
  58. struct sym *
  59. remsym(struct sym * pp)
  60. {
  61.     register struct sym **    xp, * qp;;
  62.  
  63.     xp = &sym_tab[hashit(pp->s_name, SYM_TAB)];
  64.     if(*xp == pp) {
  65.         *xp = pp->s_next;
  66.         return pp;
  67.     }
  68.     qp = *xp;
  69.     while(qp->s_next && qp->s_next != pp)
  70.         qp = qp->s_next;
  71.     if(!qp)
  72.         cerror("REMSYM error");
  73.     qp->s_next = pp->s_next;
  74.     return pp;
  75. }
  76.  
  77.  
  78. ----
  79.  Clyde Smith-Stubbs       | HI-TECH Software,       | Voice: +61 7 3300 5011
  80.  clyde@hitech.com.au      | P.O. Box 103, Alderley, | Fax:   +61 7 3300 5246
  81. http://www.hitech.com.au  | QLD, 4051, AUSTRALIA.   | BBS:   +61 7 3300 5235
  82. ----------------------------------------------------------------------------
  83. FREE! Download our shareware (FREE for noncommercial use) MS-DOS C Compiler!
  84.              Point your Web browser at http://www.hitech.com.au/
  85.